package com.zhugang.week13.hash;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @program algorithms
 * @description: relativeSortArray
 * @author: chanzhugang
 * @create: 2022/12/08 21:06
 */
public class RelativeSortArray {

    /**
     * 1122、数组的相对顺序
     * https://leetcode.cn/problems/relative-sort-array/
     *
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        /**
         * 按arr2顺序排，不在arr2中的按升序
         * arr2构建哈希表，统计arr1中包含arr2元素出现的次数, 挺考验逻辑思维
         */
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            countMap.put(arr2[i], 0);
        }
        // arr2在arr1中词频
        for (int i = 0; i < arr1.length; i++) {
            if (countMap.containsKey(arr1[i])) {
                int count = countMap.get(arr1[i]);
                countMap.put(arr1[i], count + 1);
            }
        }

        int[] result = new int[arr1.length];
        int k = 0;
        for (int i = 0; i < arr2.length; i++) {
            Integer count = countMap.get(arr2[i]);
            for (int j = 0; j < count; j++) {
                // 相同数字出现的次数
                result[k + j] = arr2[i];
            }
            k += count;
        }

        Arrays.sort(arr1);
        for (int i = 0; i < arr1.length; i++) {
            if (!countMap.containsKey(arr1[i])) {
                // 剩余数字升序追加
                result[k++] = arr1[i];
            }
        }
        return result;
    }
}